package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

/***
 * @description tree 工具类
 * @author 青石路
 * @date 2022/1/11 9:29
 */
public final class TreeUtil {

    /**
     * 初始化二叉树
     * @return
     */
    public static TreeNode<String> initBinaryTree() {
        TreeNode<String> head = new TreeNode<>("a");
        TreeNode<String> headL = new TreeNode<>("b");
        TreeNode<String> headR = new TreeNode<>("c");
        head.left = headL;
        head.right = headR;

        TreeNode<String> thirdLevel1 = new TreeNode<>("q");
        TreeNode<String> thirdLevel2 = new TreeNode<>("w");
        TreeNode<String> thirdLevel3 = new TreeNode<>("d");
        headL.left = thirdLevel1;
        headL.right = thirdLevel2;
        headR.right = thirdLevel3;

        TreeNode<String> forthLevel1 = new TreeNode<>("t");
        TreeNode<String> forthLevel2 = new TreeNode<>("u");
        thirdLevel2.left = forthLevel1;
        thirdLevel2.right = forthLevel2;

        return head;
    }

    /**
     * 逆序打印以 node 为根节点的二叉树的右边界
     * @param node
     */
    public static void printRightEdge(TreeNode node) {
        TreeNode tail = reverseRightEdge(node);
        TreeNode cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        // 逆序之后进行还原
        reverseRightEdge(tail);
    }

    /**
     * 逆序右边界
     *      和单向链表的逆序一样
     * @param node
     * @return
     */
    public static TreeNode reverseRightEdge(TreeNode node) {
        TreeNode pre = null;
        TreeNode next = null;
        while(node != null) {
            next = node.right;
            node.right = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}
